#include <fmt/format.h>
#include <list>
#include <unordered_map>
#include <utility>
class LRUCache {
public:
    int capacity;
    std::unordered_map<int, std::list<std::pair<int,int>>::iterator> cache; // key -> value
    std::list<std::pair<int, int>> order; // to keep track of the order of keys
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        auto it=cache.find(key);
        if (it!= cache.end()) {
           order.splice(order.begin(),order,it->second); 
              return it->second->second;
        }
        return -1; // Key not found
    }
    
    void put(int key, int value) {
         auto it=cache.find(key);
        if(it != cache.end()) {
            // Key exists, update value and move to front
            it->second->second = value;
            order.splice(order.begin(), order, it->second);
        } else {
            // Key does not exist
            if (cache.size() >= capacity) {
                // Cache is full, remove the least recently used key
                auto lru_key = order.back();
                cache.erase(lru_key.first);
                order.pop_back();
            }
            order.emplace_front(key, value);
            cache[key] = order.begin();
        }
    }
};

#include <gtest/gtest.h>
TEST(LRUCacheTest, BasicOperations) {
    LRUCache lru(2);
    lru.put(1, 1);
    lru.put(2, 2);
    EXPECT_EQ(lru.get(1), 1); // returns 1
    lru.put(3, 3); // evicts key 2
    EXPECT_EQ(lru.get(2), -1); // returns -1 (not found)
    lru.put(4, 4); // evicts key 1
    EXPECT_EQ(lru.get(1), -1); // returns -1 (not found)
    EXPECT_EQ(lru.get(3), 3); // returns 3
    EXPECT_EQ(lru.get(4), 4); // returns 4
}